package _greedy

import org.junit.Assert
import org.junit.Test


/**
 * 题型：动态规划 / 分治法 / 贪心算法
 *
 * 53. 最大子数组和
 * https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
 * https://leetcode.cn/problems/maximum-subarray/description/

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
 */
class leetcode_53 {
    @Test
    fun test_1() {
        val actual = maxSubArray(intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4))
        val expect = 6
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_2() {
        val actual = maxSubArray(intArrayOf(1))
        val expect = 1
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_3() {
        val actual = maxSubArray(intArrayOf(5, 4, -1, 7, 8))
        val expect = 23
        Assert.assertEquals(actual, expect)
    }

    fun maxSubArray(nums: IntArray): Int {
        /*
        贪心算法
        1 全是负数怎么？
        2 如果sum大于MaxSum，maxSum = sum
        如果sum < 0, sum = 0
        3 贪心：负数只会拉低总和
        局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
         */
        var sum: Int = 0
        var maxSum: Int = Int.MIN_VALUE
        for (n in nums) {
            sum += n
            if (sum > maxSum) {
                maxSum = sum
            }
            if (sum < 0) {
                sum = 0
            }
        }
        return maxSum
    }
}